package org.example.myleet.p1356;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    public int[] sortByBits(int[] arr) {
        Map<Integer, Integer> numberBitMap = new HashMap<>();
        Integer[] nums = new Integer[arr.length];
        for (int i=0; i<arr.length; i++) {
            numberBitMap.put(arr[i], countBit(arr[i]));
            nums[i] = arr[i];
        }
        Arrays.sort(nums, (o1, o2) -> {
            Integer o1BitCount = numberBitMap.get(o1);
            Integer o2BitCount = numberBitMap.get(o2);
            if (!o1BitCount.equals(o2BitCount)) {
                return o1BitCount - o2BitCount;
            }
            return o1 - o2;
        });
        for (int i=0; i<nums.length; i++) {
            arr[i] = nums[i];
        }
        return arr;
    }

    /**
     * 土办法求bit，除2法
     * @param a
     * @return
     */
    public int countBit(int a) {
        int count = 0;
        int b = a;
        while (b > 0) {
            if (b % 2 > 0) {
                ++count;
            }
            b /= 2;
        }
        return count;
    }
}
